#!/usr/bin/env python
"""
# -*- coding: utf-8 -*-
# @Time    : 2020/9/17 15:29
# @Author  : AshJo
# @Desc    : 二分查找
# @Filename: binary_search.py
# @Version : v1.0
"""

# 二分查找，有序数列，基于递归方式实现
# 注意：不能使用列表切片，每次切片改变了原列表的长度，同时也改变了原列表的索引

arr = [1, 3, 9, 12, 17, 20, 26, 28, 35, 39, 46, 52, 58, 63, 72, 74, 81, 83, 84, 89, 95, 99, 101]


def binarySearch(arr, x, l=0, r=len(arr) - 1):
    """
    递归二分查找
    :param arr:数列
    :param x:查找元素
    :param l:左索引
    :param r:右索引
    :return:返回 x 在 arr 中的索引，如果不存在返回 None
    """
    if r >= l:

        mid = int(l + (r - l) / 2)

        # 元素整好的中间位置
        if arr[mid] == x:
            return mid

        # 元素小于中间位置的元素，只需要再比较左边的元素
        elif arr[mid] > x:
            return binarySearch(arr, x, l, mid - 1)

        # 元素大于中间位置的元素，只需要再比较右边的元素
        else:
            return binarySearch(arr, x, mid + 1, r)

    else:
        # 不存在
        return None


if __name__ == '__main__':
    x = 3
    ret = binarySearch(arr, x)
    if ret:
        print(f"查找元素的索引为{ret},对应的值是{arr[ret]}")
    else:
        print(ret)
        print('查找的元素不存在')
